home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / BBS-Archive / Dev / Obrn-A_1.6_src.lha / oberon-a / texts2.lha / texts / Memory.txt < prev    next >
Text File  |  1995-07-02  |  13KB  |  274 lines
  1.      $RCSfile: Memory.txt $
  2.   Description: Description of the Oberon-A memory management system
  3.  
  4.    Created by: fjc (Frank Copeland)
  5.     $Revision: 1.2 $
  6.       $Author: fjc $
  7.         $Date: 1994/05/13 19:28:33 $
  8.  
  9.   Copyright © 1994, Frank Copeland.
  10.   This file is part of Oberon-A.
  11.   See Oberon-A.doc for conditions of use and distribution.
  12.   ________________________________________________________________________
  13.  
  14.  
  15.   Introduction
  16.   ------------
  17.  
  18.   This document describes the design and implementation of Oberon-A's
  19.   memory management.  This covers the allocator (NEW and SYSTEM.NEW),
  20.   deallocator (SYSTEM.DISPOSE) and garbage collector (SYSTEM.GC).  The
  21.   design used for Oberon-A is based closely on the designs discussed in
  22.   the Oberon Technical Notes 2 and 5, (see TechNotes.doc).
  23.  
  24.   Memory blocks
  25.   -------------
  26.  
  27.   Memory allocation in Oberon must take into account a number of factors
  28.   that require more than just requesting a block of memory from the
  29.   operating system.  Oberon's run-time type checking requires that every
  30.   record variable that is dynamically allocated have an hidden type tag
  31.   preceding it.  The garbage collector must be able to distinguish between
  32.   memory allocated for records, arrays and untyped blocks (created by
  33.   SYSTEM.NEW).  CPointers and BPointers must be treated differently to
  34.   normal Oberon pointers.
  35.  
  36.   Three types of memory block are recognised:
  37.  
  38.     RecordBlk : memory allocated to a POINTER TO <record type> variable.
  39.     ArrayBlk  : memory allocated to a POINTER TO <array type> variable.
  40.     SysBlk    : memory allocated to a CPointer or BPointer variable, or
  41.                 allocated with SYSTEM.NEW.
  42.  
  43.   A RecordBlk looks like this, where v is a variable of type POINTER TO T,
  44.   T is a record type:
  45.  
  46.       RecordBlk = RECORD
  47.         link : ADDRESS; (* next element in list of blocks *)
  48.         tag  : ADDRESS; (* type descriptor of type T *)
  49.   v --> data : ARRAY SIZE(T) OF BYTE
  50.       END
  51.  
  52.   An ArrayBlk looks like this, where v is a variable of type POINTER TO
  53.   ARRAY n1, n2 ... ni-1 OF T:
  54.  
  55.       ArrayBlk = RECORD
  56.         arrpos   : LONGINT; (* used by the garbage collector *)
  57.         elemSize : LONGINT; (* SIZE (T), for the convenience of the
  58.                                garbage collector *)
  59.         size     : LONGINT; (* n1 * n2 ... * ni-1 * SIZE(T) *)
  60.         link     : ADDRESS; (* next element in list of blocks *)
  61.         tag      : ADDRESS; (* type descriptor of type T *)
  62.   v --> data     : ARRAY size OF BYTE
  63.       END
  64.  
  65.   A SysBlk looks like this, where v is any pointer variable:
  66.  
  67.       SysBlk = RECORD
  68.         link : ADDRESS; (* next element in list of blocks *)
  69.         size : LONGINT; (* size of block *)
  70.   v --> data : ARRAY size OF BYTE
  71.       END
  72.  
  73.   The type of the block is determined by bits encoded in the tag or size
  74.   field at address: v - 4.  Bits 0 and 1 are used for this encoding: they
  75.   are available to be used because the type descriptors are guaranteed to
  76.   be longword-aligned and the allocator ensures that block sizes are
  77.   multiples of 4 bytes.  Bit 0 is set to indicate that the block is a
  78.   SysBlk.  Bit 1 is set to indicate that the block is an ArrayBlk.  If bit
  79.   1 is clear, the block is a RecordBlk.  This encoding ensures that the
  80.   type tag of a RecordBlk is a valid pointer to a type descriptor, which
  81.   is necessary for fast run-time type checks and guards.  For the other
  82.   block types, the encoded bits must be masked out before the tag or size
  83.   field can be used.
  84.  
  85.   The link field (at address: v - 8) in each type of block is used to
  86.   implement a singly-linked list of allocated blocks.  It is either NIL,
  87.   or points to the link field in the next block in the list.  Blocks are
  88.   added to the list by the allocator and removed by the deallocator and
  89.   garbage collector.  All allocated blocks are freed when the program
  90.   terminates.  Two seperate lists are maintained: one of traced blocks
  91.   known to the garbage collector and one of untraced blocks.
  92.  
  93.   The size, elemSize and arrpos fields in an ArrayBlk block are required
  94.   by the garbage collector (see Garbage collection).
  95.  
  96.   Allocating memory
  97.   -----------------
  98.  
  99.   The allocator is implemented in two procedures in the run-time support
  100.   library: OberonSys_NEW and OberonSys_SYSNEW.  OberonSys_NEW is used to
  101.   allocate RecordBlk and ArrayBlk blocks and OberonSys_SYSNEW is used to
  102.   allocate SysBlk blocks.  The standard procedure SYSTEM.NEW always
  103.   translates into a call to OberonSys_SYSNEW while the standard procedure
  104.   NEW can translate into a call to either, depending on the type of
  105.   variable.
  106.  
  107.   Oberon_NEW requires two parameters:
  108.  
  109.     size (passed D0): this is only required for an ArrayBlk and is the
  110.       size of the block to be allocated.
  111.  
  112.     tag (passed in D1): a pointer to a type descriptor. Bit 1 is set if an
  113.       ArrayBlk is required.
  114.  
  115.   For a RecordBlk block, OberonSys_NEW calculates the size of the block by
  116.   adding 8 to the size of the record found in the type descriptor.  For an
  117.   ArrayBlk block, it adds 20 to the size parameter.  The result is rounded
  118.   up to the next multiple of 4 bytes.  It then asks Exec for a block of
  119.   memory of the required size, using AllocMem (size, {memClear}) so that
  120.   the block is zeroed.  If successful, it initialises the block's hidden
  121.   fields, links it into the relevant list and returns the address of the
  122.   data field in D0.  By default, the allocated block is placed in the
  123.   list of blocks known to the garbage collector.  If the allocation fails,
  124.   NIL is returned in D0.
  125.  
  126.   OberonSys_SYSNEW requires two parameters:
  127.  
  128.     size (passed in D0): the number of bytes to be allocated.
  129.     traced (passed in D1.B): a flag indicating if the variable is traced.
  130.  
  131.   OberonSys_SYSNEW adds 8 to the size parameter and rounds the result up
  132.   to the next multiple of 4 bytes.  It then asks Exec for a block of
  133.   memory of the required size, using AllocMem (size, {memClear}) so that
  134.   the block is zeroed.  If successful, it initialises the block's hidden
  135.   fields, links it into the relevant list and returns the address of the
  136.   data field in D0.  If traced is TRUE, the allocated block is placed in
  137.   the list of blocks known to the garbage collector, otherwise it is
  138.   placed in an alternate list and will not be garbage collected.  If the
  139.   allocation fails, NIL is returned in D0.
  140.  
  141.   Type tags and descriptors
  142.   -------------------------
  143.  
  144.   RecordBlk and ArrayBlk blocks both contain a type tag, which is a
  145.   pointer to a type descriptor.  A type descriptor is always associated
  146.   with a record type.  Information in the type descriptor is used by the
  147.   allocator and the garbage collector.  The structure of a type descriptor
  148.   is:
  149.  
  150.     TypeTag = POINTER TO TypeDesc;
  151.     TypeDesc = RECORD
  152.       size    : LONGINT;
  153.       ttable  : ARRAY 8 OF TypeTag;
  154.       offsets : ARRAY N+1 OF LONGINT
  155.     END
  156.  
  157.   size holds the size in bytes of an object of that type.  This is used
  158.   by the allocator to determine the size of a RecordBlk.  ttable holds a
  159.   table of pointers to the descriptors of the base types of the
  160.   descriptor's type. This is used in type tests and guards.  The size is
  161.   fixed so that the garbage collector can always locate the offsets field
  162.   at a fixed offset from the base of the type descriptor.  This limits the
  163.   depth to which types can be extended.  The depth chosen (8) is the same
  164.   as that used in the Oberon System and should be adequate for most
  165.   purposes. The offsets field is an array holding the offsets of the
  166.   pointer fields in the type; N is the number of such fields.  This is
  167.   used in the garbage collector's mark phase (see Garbage collection).
  168.  
  169.   Deallocating memory
  170.   -------------------
  171.  
  172.   Memory is explicitly deallocated with the standard procedure
  173.   SYSTEM.DISPOSE.  This is implemented in the run-time support procedure
  174.   OberonSys_DISPOSE.
  175.  
  176.   OberonSys_DISPOSE has one parameter:
  177.  
  178.     block (passed in D0): the address of the block to be freed.
  179.  
  180.   OberonSys_DISPOSE scans the lists of allocated blocks looking for block;
  181.   the untraced list is scanned first.  If it does not find block, it halts
  182.   the program.  Otherwise, block is removed from the list and the memory
  183.   is returned to the operating system using the Exec function FreeMem.
  184.  
  185.   SYSTEM.DISPOSE was originally intended to take the place of the garbage
  186.   collector, which was not implemented until version 0.4 of the compiler.
  187.   Wherever possible, the garbage collector should be relied on instead,
  188.   especially if there is any chance that a block will be assigned to more
  189.   than one variable.  The use of SYSTEM.DISPOSE should be restricted to
  190.   freeing untraced variables and variables that are strictly local to a
  191.   single procedure.
  192.  
  193.   Garbage collection
  194.   ------------------
  195.  
  196.   Garbage is dynamically allocated memory that is no longer referenced by
  197.   any variable.  If it is not freed, it will cause memory leaks and
  198.   fragmentation.  On the other hand, memory freed while variables still
  199.   reference it may cause bugs due to dangling pointers.  The safest way to
  200.   free garbage is by using a garbage collector, which traces all pointer
  201.   variables to determine which memory is still being referenced.
  202.  
  203.   The original design of the Oberon language assumed that it would be
  204.   operating in an environment which provided automatic garbage collection.
  205.   As a result, the language contains a NEW procedure, but no DISPOSE.
  206.   This assumption was later modified and implementators are now expected
  207.   to provide a SYSTEM.DISPOSE procedure if they do not implement a garbage
  208.   collector.  Oberon-A now provides both.  It implements the collector in
  209.   the OberonSys_GC procedure in the run-time support code of each program.
  210.  
  211.   The garbage collector must be explicitly activated by the program
  212.   calling the standard procedure SYSTEM.GC.  The current implementation is
  213.   not able to locate pointer variables on the stack; it can only trace
  214.   global variables.  This means that the garbage collector must *not* be
  215.   activated at any point in the program where pointer variables local to
  216.   an active procedure are referencing allocated memory.  This will
  217.   typically restrict it to the main body of the program, or the main event
  218.   loop, where the programmer can guarantee that only global variables
  219.   contain references to dynamically allocated memory.  If a program does
  220.   not call SYSTEM.GC, all dynamically allocated memory will remain
  221.   allocated until the program ends.  In many cases, especially in small
  222.   utility programs, this will be preferable.
  223.  
  224.   The Oberon-A collector uses a mark-and-sweep algorithm.  It first marks
  225.   the allocated memory blocks that are reachable through global variables.
  226.   It then sweeps through all the allocated blocks, freeing any that were
  227.   not found in the mark phase.  The algorithm used for the mark phase of
  228.   the collector is described in the Oberon Technical Notes, part 5; see
  229.   also part 2 for an earlier version of the algorithm.  The sweep phase
  230.   consists of scanning the list of traced blocks built by the allocator,
  231.   freeing the unmarked blocks and unmarking the marked ones.
  232.  
  233.   The garbage collector must be able to find the global variables of each
  234.   module in the program.  To enable this, the compiler creates a data hunk
  235.   for each module with global pointer variables called "<module name>_GC".
  236.   This hunk has the following structure:
  237.  
  238.     GCHunkPtr = POINTER TO GCHunk;
  239.     GCHunk = RECORD
  240.       link    : GCHunkPtr;
  241.       varBase : ADDRESS;
  242.       vars    : ARRAY N+1 OF LONGINT
  243.     END; (* GCHunk *)
  244.  
  245.   The hunks for all of a program's modules are inserted in a singly linked
  246.   list through the link field in each hunk.  The list is anchored in a
  247.   global variable called OS_GCVars in the run-time support code.  The
  248.   initialisation code of each module ensures that the module's hunk is
  249.   inserted in the list.  The varBase points to the base of the module's
  250.   variables.  The vars field is a list of offsets from varBase, one for
  251.   each pointer variable.  The end of the list is marked by a negative
  252.   offset.
  253.  
  254.   The mark phase of the collector starts at the hunk pointed to by
  255.   OS_GCVars and follows the pointers in the link fields of all the hunks
  256.   in the list, marking the variables listed in each hunk.  CPointer and
  257.   BPointer variables are not traced by the garbage collector.  A RecordBlk
  258.   or ArrayBlk block may itself contain pointers to other blocks.  The
  259.   collector must mark these variables as well.  To do this it uses the
  260.   information in the type descriptor pointed to by the type tag in each
  261.   block.  See Type tags and descriptors.
  262.  
  263.   A block is marked by setting a bit in the block's type tag.  This
  264.   presents a problem, since the available low-order bits are already used
  265.   to encode the block type.  The most-significant bit is used instead:
  266.   when it is set, the block is marked.  This bit was chosen on the
  267.   assumption that it is extremely unlikely to be used in a valid address
  268.   for a type descriptor.  This is a fairly safe assumption, as few Amigas
  269.   have more than 2GB of memory installed, but in theory this might lead to
  270.   problems.  As a belt-and-braces concession to safety, the memory
  271.   allocator checks this bit in any type tag passed to it and halts the
  272.   program if it is set.
  273.  
  274.